package A1动态规划;

import java.util.Arrays;

public class LC_647回文子串 {
    public static void main(String[] args){
        String s = "abc";
        System.out.println(countSubstrings(s));
    }

    public static int countSubstrings(String s) {
        int result=0;
        char[] c=s.toCharArray();
        int len=c.length;
        boolean[][] dp=new boolean[len][len];
        for(int i=len-1;i>=0;i--)
            for(int j=i;j<len;j++){
                if(c[i]==c[j]){
                    if(j-i<=1){
                        dp[i][j]=true;
                        result++;
                    }
                    else if(dp[i+1][j-1]==true){
                        dp[i][j]=true;
                        result++;
                    }
                }
            }
        return result;
    }
}
